package NewCode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author wangchenghao
 * @date 2021/7/22
 **/
public class NC38 {
    public ArrayList<Integer> spiralOrder(int[][] matrix){
        ArrayList<Integer> ans=new ArrayList<Integer>();
        int m=matrix.length;
        if (m==0){
            return ans;
        }
        int n=matrix[0].length;
        if(n==0){
            return ans;
        }
        boolean[][] visit=new boolean[m][n];
        int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
        int t=0;//走哪个方向，0 右 1 下 2 左 3 上
        int x=0,y=0;
        boolean end=false;
        while(!end){
            ans.add(matrix[x][y]);
            visit[x][y]=true;
            //如果现在的位置四个方向都不能走了，循环就可以结束了
            for(int i=0;i<5;i++){
                //循环结束
                if(i==4){
                    end=true;
                    break;
                }
                int tx=x+dir[t][0];
                int ty=y+dir[t][1];
                if(tx>=0&&tx<m&&ty>=0&&ty<n && !visit[tx][ty]){
                    x=tx;
                    y=ty;
                    break;
                }else {
                    t=(t+1)%4;
                }
            }
        }
        return  ans;
    }
}
